import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Merge {
    //leetcode 合并区间
    // https://leetcode.cn/problems/merge-intervals/description/
    public int[][] merge(int[][] intervals) {
        // 先对数组进行排序，现根据左区间进行排序，如果左区间相等，再以右区间排序
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            else return a[0] - b[0];
        });
        int start = intervals[0][0], end = intervals[0][1];
        List<int[]> ret = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > end) {
                ret.add(new int[]{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
            else {
                end = Math.max(end,intervals[i][1]);
            }
        }
        ret.add(new int[]{start,end});
        return ret.toArray(new int[][]{});
    }
}
